/*
 * @lc app=leetcode.cn id=686 lang=typescript
 *
 * [686] 重复叠加字符串匹配
 */

// @lc code=start
function repeatedStringMatch(a: string, b: string): number {
  // next数组
  const getNext = (patten: string): number[] => {
    const m = patten.length;
    const res: number[] = new Array(m).fill(-1);
    for (let i = 1, j = -1; i < m; i++) {
      while (j !== -1 && patten[j + 1] !== patten[i]) {
        j = res[j];
      }
      if (patten[j + 1] === patten[i]) {
        j++;
      }
      res[i] = j;
    }
    return res;
  };
  // KMP算法
  const kpm = (text: string, patten: string): number => {
    const next = getNext(patten);
    const n = text.length;
    const m = patten.length;
    // i和j的差值不能超过n
    for (let i = 0, j = -1; i - (j + 1) < n; i++) {
      while (j !== -1 && text[i % n] !== patten[j + 1]) {
        j = next[j];
      }
      if (text[i % n] === patten[j + 1]) {
        j++;
      }
      console.log(i, j);
      if (j === m - 1) {
        return i - j;
      }
    }
    return -1;
  };

  const n = a.length;
  const m = b.length;
  const index = kpm(a, b);

  if (index === -1) {
    return -1;
  }
  // 返回结果
  return Math.ceil((m + index) / n);
}
// @lc code=end
